A distributed database management system (“DBMS”) may allow for the storage and retrieval of data that is distributed among multiple computing nodes. Data in a distributed DBMS may be organized into tables, which in turn may comprise collections of items sometimes described as table partitions. To improve the performance, reliability and availability of the system, each table partition may each be housed on a separate computing node that processes requests to store and retrieve the items it houses. A distributed database may also employ replication to maintain standby table partitions that may be employed in the event of a system failure.
Indexes may be described as data structures that allow items stored in a distributed DBMS to be located. They may, for example, allow items falling within a particular range of data to be located by scanning the index rather than searching through all of the items stored on one or more of the partitions. In order to maintain the integrity of an index with respect to data maintained in an associated table, entries in an index are updated based on changes made to corresponding data in the table. Indexes may also be partitioned, and there may be multiple indexes associated with a table.